Search results for "Mathematical Foundations of Computer Science"
showing 4 items of 4 documents
Unconventional Finite Automata and Algorithms
2016
Elektroniskā versija nesatur pielikumus
Limitations of Quantum Walks and Randomized Algorithms
2019
Šajā darbā tiek pētīta algoritmu sarežģītība dažādos skaitļošanas modeļos. Konkrētāk, tiek pētītas kvantu klejošanas algoritmu īpašības un ierobežojumi, kā arī varbūtisko vaicājumalgoritmu darbības laika novērtēšanas metodes. Pirmajā daļā tiek aplūkotas Grovera kvantu klejošana un meklēšana grafos. Darbā tiek sniegts vispārīgs matemātisks apraksts klejošanas lokalizācijai un meklēšanas stacionārajiem stāvokļiem. Otrajā daļā tiek aplūkotas apakšējo novērtējumu metodes varbūtisko vaicājumalgoritmu modelī. Darbā tiek pierādīta klasisko pretinieka metožu asimptotiskā ekvivalence visur definētām funkcijām, un aprakstītas to atšķirības daļēji definētām funkcijām. Tiek arī aplūkota saistība starp …
Probabilistic computation and verification beyond Turing machines
2019
Mūsu mērķis ir izpētīt dažādus ierobežotas kļūdas varbūtiskus modeļus, kas spēj definēt nesanumurējami daudz valodu. Mēs sākam ar stingrāko nosacījumu - sākumā apskatām minimālus modeļus, kas var atpazīt visas valodas. Mēs apskatām varbūtiskas Tjūringa mašīnas, varbūtiskus automātus ar skaitītājiem un varbūtiskus galīgus automātus ar dažādiem ierobežojumiem uz ievadgalviņu. Mēs apskatām arī konstantas telpas pārbaudītājus (verifiers), kas mijiedarbojas ar vienu un diviem pierādītājiem (provers) un pārbauda (verify) visas valodas. Pēc tam mēs pieminētajos modeļos apskatām nesanumurējami daudzu valodu atpazīšanu un pārbaudi ar ierobežotu kļūdu. Mēs pierādām arī jaunus rezultātus par kvantu au…
The Power and the Limits of Quantum Automata and Search Algorithms
2013
Kvantu skaitļošana ir nozare, kas pēta uz kvantu mehānikas likumiem balstīto skaitļošanas modeļu īpašības. Disertācija ir veltīta kvantu skaitļošanas algoritmiskiem aspektiem. Piedāvāti rezultāti trijos virzienos: Kvantu galīgi automāti Analizēta stāvokļu efektivitāte kvantu vienvirziena galīgam automātam. Uzlabota labāka zināmā eksponenciālā atšķirība [AF98] starp kvantu un klasiskajiem galīgajiem automātiem. Grovera algoritma analīze Pētīta Grovera algoritma noturība pret kļūdām. Vispārināts [RS08] loģisko kļūdu modelis un piedāvāti vairāki jauni rezultāti. Kvantu klejošana Pētīta meklēšana 2D režģī izmantojot kvantu klejošanu. Paātrināts [AKR05] kvantu klejošanas meklēšanas algoritms. At…